#include <iostream>
#include <vector>
#include "MyHash.hpp"
#include <ctime>

using namespace std;
using namespace close_hash;
using namespace open_hash;

// 整数查找
// void close_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashTable<int, int> h;
//     int keyLen = 10;
//     vector<int> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         int key = rand() % 10000, value = rand() % 1999;
//         keyArr[i] = key;
//         h.insert(make_pair(key, value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << key << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前容量: " << h.capacity() << endl;
//         cout << "当前负载因子: " << h.loadfactor() << endl;
//         cout << "-------------------------\n"; 
//     }

//     for (int i = 0; i < keyLen; ++i)
//     {
//         HashElem<int, int>* elem = h.find(keyArr[i]);
//         if (elem == nullptr)
//         {
//             cout << "哈希表存在问题，请检查后测试！" << endl;
//             break;
//         }
//         cout << "key: " << elem->kv.first << " value: " << elem->kv.second << endl;
//     }
// }

// 字符串检查
// void close_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashTable<string, int> h;
//     int keyLen = 20;
//     vector<string> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;
//         keyArr[i] = str;
//         h.insert(make_pair(keyArr[i], value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << str << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前容量: " << h.capacity() << endl;
//         cout << "当前负载因子: " << h.loadfactor() << endl;
//         cout << "-------------------------\n"; 
//     }

//         for (int i = 0; i < keyLen; ++i)
//         {
//             HashElem<string, int>* elem = h.find(keyArr[i]);
//             if (elem == nullptr)
//             {
//                 cout << "哈希表存在问题，请检查后测试！" << endl;
//                 break;
//             }
//             cout << "key: " << elem->kv.first << " value: " << elem->kv.second << endl;
//         }
// }

// 实际比较查找时间
// void close_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));

//     HashTable<string, int> h;
//     vector<pair<string, int>> strArr;

//     int keyLen = 20000;
//     strArr.resize(keyLen);

//     vector<string> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;
//         keyArr[i] = str;
//         h.insert(make_pair(keyArr[i], value));
//         strArr[i] = make_pair(keyArr[i], value);
//     }

//     pair<string, int> kv;

//     // 随机在数组内查找
//     clock_t time1, time2;
//     clock_t time_strArr = 0, time_closeHash = 0;

//     int n = keyLen;
//     vector<bool> keyexist1(keyLen, false);

//     // 普通数组On遍历
//     while (n)
//     {
//         int num = rand() % keyLen;
//         while (keyexist1[num])
//         {
//             // 找到没有被使用的
//             num = rand() % keyLen;
//         }
//         keyexist1[num] = true;
//         --n;  // 可用下标数减一

//         time1 = clock();
//         for(int i = 0; i < keyLen; ++i)
//         {
//             if (strArr[i].first == keyArr[num]){
//                 kv = strArr[i];
//                 break;
//             }
//         }
//         time2 = clock();
//         time_strArr += (time2 - time1);
//         // cout << "key-value: " << kv.first << ": " << kv.second << endl;
//     }

//     // cout << endl << endl;
//     // 闭散列哈希表查找
//     n = keyLen;
//     vector<bool> keyexist2(keyLen, false);
//     while (n)
//     {
//         int num = rand() % keyLen;
//         while (keyexist2[num])
//         {
//             // 找到没有被使用的
//             num = rand() % keyLen;
//         }
//         keyexist2[num] = true;
//         --n;  // 可用下标数减一

//         HashElem<string, int>* temp;
//         time1 = clock();
//         temp = h.find(keyArr[num]);
//         time2 = clock();
//         time_closeHash += (time2 - time1);
//         kv= temp->kv;
//         // cout << "key-value: " << kv.first << ": " << kv.second << endl;
//     }

//     cout << "----------------------------\n";
//     cout << "time_strArr: " << time_strArr << endl;
//     cout << "time_closeHash: " << time_closeHash << endl;
// }

// 测试插入和删除
// void close_hash_test()
// {
//     HashTable<string, int> h;
//     h.insert(make_pair("你好", 15));
//     h.insert(make_pair("a", 11));
//     h.insert(make_pair("b", 12));
//     h.insert(make_pair("c", 1));
//     h.insert(make_pair("d", 3));
//     h.insert(make_pair("e", 4));
//     h.insert(make_pair("f", 6));
//     h.erase("c");
//     h.insert(make_pair("c", 9));
//     h.insert(make_pair("de", 9));

//     cout << "正常" << endl;
// }

// 整数查找
// void open_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashBucket<int, int> h;
//     int keyLen = 10;
//     vector<int> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         int key = rand() % 10000, value = rand() % 1999;
//         keyArr[i] = key;
//         h.insert(make_pair(key, value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << key << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前桶数: " << h.BucketCount() << endl;
//         cout << "-------------------------\n"; 
//     }

//     for (int i = 0; i < keyLen; ++i)
//     {
//         HashBucketNode<int, int>* node = h.find(keyArr[i]);
//         if (node == nullptr)
//         {
//             cout << "哈希表存在问题，请检查后测试！" << endl;
//             break;
//         }
//         cout << "key: " << node->kv.first << " value: " << node->kv.second << endl;
//     }
// }

// 字符串检查
// void open_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashBucket<string, int> h;
//     int keyLen = 20;
//     vector<string> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;
//         keyArr[i] = str;
//         h.insert(make_pair(keyArr[i], value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << str << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前桶数: " << h.BucketCount() << endl;
//         cout << "-------------------------\n"; 
//     }

//         for (int i = 0; i < keyLen; ++i)
//         {
//             HashBucketNode<string, int>* node = h.find(keyArr[i]);
//             if (node == nullptr)
//             {
//                 cout << "哈希表存在问题，请检查后测试！" << endl;
//                 break;
//             }
//             cout << "key: " << node->kv.first << " value: " << node->kv.second << endl;
//         }
// }

// 两个哈希效率测试
// 以插入、删除、随机查找三种综合效率进行测试
void hash_efficiency()
{
    // 时间种子
    srand((unsigned int)time(nullptr));
    // 
    clock_t time1, time2;
    clock_t open_insert, close_insert, open_erase, close_erase, open_find, close_find;

    HashTable<string, int> h1;
    HashBucket<string, int> h2;

    int keyLen = 200000;

    vector<pair<string, int>> keyArr(keyLen);
    
    for (int i = 0; i < keyLen; ++i)
    {
        // 生成1~6长度的随机字符串作为key进行测试
        int num = rand() % 6 + 1;
        string str;
        for (int i = 0; i < num; ++i)
        {
            int fes = rand() % 26;
            str += ('a' + fes);
        }

        int value = rand() % 1999;

        keyArr[i].first = str;
        keyArr[i].second = value;
    }

    // 插入测试
    // close
    time1 = clock();
    for (auto& kv : keyArr)
    {
        h1.insert(kv);
    }
    time2 = clock();
    close_insert = time2 - time1;
    // open
    time1 = clock();
    for (auto& kv : keyArr)
    {
        h2.insert(kv);
    }
    time2 = clock();
    open_insert = time2 - time1;

    // 查找测试
    // close
    time1 = clock();
    for (auto& kv : keyArr)
    {
        if (!h1.find(kv.first))
        {
            cout << "h1: find出错了！" << endl;
            break;  // 防止刷屏
        } 
    }
    time2 = clock();
    close_find = time2 - time1;
    // open
    time1 = clock();
    for (auto& kv : keyArr)
    {
        if (!h2.find(kv.first))
        {
            cout << "h2: find出错了！" << endl;
            break;  // 防止刷屏
        } 
    }
    time2 = clock();
    open_find = time2 - time1;

    // 删除测试
    time1 = clock();
    for (auto& kv : keyArr)
    {
        h1.erase(kv.first);
    }
    time2 = clock();
    close_erase = time2 - time1;
    // open
    time1 = clock();
    for (auto& kv : keyArr)
    {
        h2.erase(kv.first);
    }
    time2 = clock();
    open_erase = time2 - time1;



    cout << "----------------------------\n";
    cout << "insert:\n";
    cout << "\tclose_insert:" << close_insert << endl;
    cout << "\topen_insert:" << open_insert << endl;
    cout << "find:\n";
    cout << "\tclose_find:" << close_find << endl;
    cout << "\topen_find:" << open_find << endl;
    cout << "erase:\n";
    cout << "\tclose_erase:" << close_erase << endl;
    cout << "\topen_erase:" << open_erase << endl;
    cout << "综合评价:\n";
    time_t close_hash = (close_insert+close_find+close_erase);
    cout << "\tclose_hash: " << close_hash << endl;
    time_t open_hash = (open_insert+open_find+open_erase);
    cout << "\topen_hash: " << open_hash << endl;
    time_t maxi = max(close_hash, open_hash);
    time_t mini = min(close_hash, open_hash);
    cout << "时间倍率为: " << maxi / mini << endl;
    cout << "----------------------------\n";
}


int main()
{
    // close_hash_test();  // 闭散列哈希表测试
    // open_hash_test();  // 开散列哈希桶测试
    hash_efficiency();// 闭散列-线性探测和开散列效率测试
    return 0;
}